index.md (3489B)
1 +++ 2 title = 'Race conditions & mutual exclusion' 3 +++ 4 # Race conditions & mutual exclusion 5 programs can race each other and come to wrong conclusions. 6 7 ## Mutual exclusion 8 critical region: a code region with access to shared resources 9 10 the conditions for mutual exclusion: 11 1. no two processes can be simultaneously in their critical regions 12 2. no assumptions can be made about speed/number of CPUs 13 3. no process running outside critical region may block others 14 4. no process should have to wait forever to enter critical region 15 16 non-solutions 17 18 - disable interrupts (disable reallocation of CPU). if you have multiple processors, shit gets fucked. 19 - lock variables (guard critical regions with booleans). so now the race is on the lock variables, great job dude. 20 - strict alternation (be nice and take turns). doesn’t allow processes to enter critical regions twice in a row, and a process outside the critical region can block another one. 21 22 Peterson's algorithm 23 24 - software solution 25 - spin lock in the while loop 26 27 ```c 28 #define N 2 29 int turn; 30 int interested[N]; 31 32 void enter_region(int process){ 33 int other = 1 - process; 34 interested[process] = TRUE; 35 turn = process; 36 while(turn==process && interested[other]==TRUE); 37 } 38 39 void leave_region(int process) { 40 interested[process] = FALSE; 41 } 42 ``` 43 44 TSL instruction 45 46 - hardware-assisted solution to mutual exclusion problem 47 - atomic test and set of a memory value 48 - spin until LOCK is acquired 49 50 ``` 51 enter_region: 52 TSL REGISTER, LOCK | copy LOCK to register, set LOCK to 1 53 CMP REGISTER, #0 | was LOCK zero? 54 JNE ENTER_REGION | if it was non-zero LOCK was set, so loop 55 RET | return to caller; critical region entered 56 57 leave_region: 58 MOVE LOCK, #0 | store a 0 in LOCK 59 RET | return to caller 60 ``` 61 62 ## Avoiding busy waiting 63 so far, CPU busy waits until it can enter the critical region (spin lock). 64 so, let process waiting return CPU to scheduler voluntarily. 65 66 ```c 67 void sleep() { 68 set own state to BLOCKED; 69 give CPU to scheduler; 70 } 71 72 void wakeup(process) { 73 set state of process to READY; 74 give CPU to scheduler; 75 } 76 ``` 77 78 Producer-consumer 79 80 - producer sleeps when buff is full 81 - consumer sleeps when buff is empty 82 83  84 85 - problem: wake up process may get lost. only wake up producer when count is N-1, but producer sleeps when count is N. 86 87 Semaphores 88 89 - introduce sema integer type with operations: 90 - down: if sema ≤ 0, block calling process. sema-- otherwise. 91 - up: if there is process blocking on sema, wake it up. sema++ otherwise. 92 - OS guarantees that all the operations are atomic (happening instantaneously) by design — disable interrupts on single processors, spin locking on multiprocessors. 93 - mutex (mutual exclusion) variable serialises access to shared buffer 94 95  96 97 Monitors 98 99 - semaphores introduce chaos in programs (gotta set all them bits) 100 - monitors: serialise procedure calls on a module, use condition vars to wait/signal processes 101 - but this needs dedicated language support 102 103  104 105 ## Message passing: solution to process sync and communication 106 107 - processes interact by sending & receiving messages. 108 - most common in multiserver OS designs 109 - issues — mem copying vs register passing (efficiency), mailboxes vs rendezvous